Robust Recursive Quadratic Programming Algorithm Model with Global and Superlinear Convergence Properties

A new, robust recursive quadratic programming algorithm model based on a continuously differentiable merit function is introduced. The algorithm is globally and superlinearly convergent, uses automatic rules for choosing the penalty parameter, and can efficiently cope with the possible inconsistency of the quadratic search subproblem. The properties of the algorithm are studied under weak a priori assumptions; in particular, the superlinear convergence rate is established without requiring strict complementarity. The behavior of the algorithm is also investigated in the case where not all of the assumptions are met. The focus of the paper is on theoretical issues; nevertheless, the analysis carried out and the solutions proposed pave the way to new and more robust RQP codes than those presently available.     

Zero-sum Markov games and worst-case optimal control of queueing systems

Zero-sum stochastic games model situations where two persons, called players, control some dynamic system, and both have opposite objectives. One player wishes typically to minimize a cost which has to be paid to the other player. Such a game may also be used to model problems with a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknown to the controller, and may vary in time in an unpredictable way. A worst-case criterion may be considered, where the unknown parameter is assumed to be chosen by nature (called player 1), and the objective of the controller (player 2) is then to design a policy that guarantees the best performance under worst-case behaviour of nature. The purpose of this paper is to present a survey of stochastic games in queues, where both tools and applications are considered. The first part is devoted to the tools. We present some existing tools for solving finite horizon and infinite horizon discounted Markov games with unbounded cost, and develop new ones that are typically applicable in queueing problems. We then present some new tools and theory of expected average cost stochastic games with unbounded cost. In the second part of the paper we present a survey on existing results on worst-case control of queues, and illustrate the structural properties of best policies of the controller, worst-case policies of nature, and of the value function. Using the theory developed in the first part of the paper, we extend some of the above results, which were known to hold for finite horizon costs or for the discounted cost, to the expected average cost.     

ɛ-Duality theorem of nondifferentiable nonconvex multiobjective programming

This technical reply deals with the relations between Ref. 1 and Refs. 2–4.     

A network penalty method

We consider the minimum cost network flow problem and describe how the non-linear penalty function methods of Conn and Bartels can be specialized to a combinatorial algorithm for this problem. We report on preliminary computational results which show that this method can require fewer pivots than the simplex method while the amount of work required for each pivot is comparable. The algorithm can be proven finite using a modification of Cunningham's strongly feasible basis pivoting rule.Supported by the Natural Sciences and Engineering Research Council of Canada, and the joint research project Combinatorial Optimization of the Natural Sciences and Engineering Research Council, Canada and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

Linear programming by minimizing distances

To solve the linear program (LP): minimizec ^T l subject toA l+b0, for ann×d-matrixA, ann-vectorb and ad-vectorc, the positive orthantS and the planeE(t) are defined by S={(x₁,x)ⁿ⁺¹ ¦(x₁,x)0}, E(t)={(x₁,x)ⁿ⁺¹¦x₁=–c ^c l+t, x=Al+b}. First a geometric algorithm is given to determine d(E(t),S) for fixedt, where d(·,·) denotes euclidean distance. This algorithm is used to construct a second algorithm to find the minimalt with E(t) S , and thus solve LP. It is shown that all algorithms are finite.     

On the Design of Optimization Strategies Based on Global Response Surface Approximation Models

Striking the correct balance between global exploration of search spaces and local exploitation of promising basins of attraction is one of the principal concerns in the design of global optimization algorithms. This is true in the case of techniques based on global response surface approximation models as well. After constructing such a model using some initial database of designs it is far from obvious how to select further points to examine so that the appropriate mix of exploration and exploitation is achieved. In this paper we propose a selection criterion based on the expected improvement measure, which allows relatively precise control of the scope of the search. We investigate its behavior through a set of artificial test functions and two structural optimization problems. We also look at another aspect of setting up search heuristics of this type: the choice of the size of the database that the initial approximation is built upon.     

Weighted nonlinear phase shift with group velocity dispersion to assess the nonlinear penalty in C+L band long-haul fiber optical amplified transmission link

To assess the penalty due to nonlinear effect in C L band long-haul optical amplified transmission link,a new parameter of modified nonlinear phase shift (φD) is proposed,which is the accumulated nonlinear phase shift weighted by a normalized group velocity dispersion (GVD).Based on the numerical simulation result of broadband long-haul hybrid Raman/erbium-doped fiber amplified transmission line,it is validated that φD is more reasonable and suitable than the previous proposed nonlinear phase shift (φNL) for broadband applications.     

Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities

The alternating direction method is one of the attractive approaches for solving linearly constrained separate monotone variational inequalities. Experience on applications has shown that the number of iterations depends significantly on the penalty parameter for the system of linear constraint equations. While the penalty parameter is a constant in the original method, in this paper we present a modified alternating direction method that adjusts the penalty parameter per iteration based on the iterate message. Preliminary numerical tests show that the self-adaptive adjustment technique is effective in practice.     

On the Superlinear Convergence Order of the Logarithmic Barrier Algorithm

Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter r_k +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if r_k+1=r _k with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods.     

Boundary penalty finite element methods for blending surfaces, . Superconvergence and stability and examples

This paper is Part III of the study on blending surfaces by partial differential equations (PDEs). The blending surfaces in three dimensions (3D) are taken into account by three parametric functions, x(r,t),y(r,t) and z(r,t). The boundary penalty techniques are well suited to the complicated tangent (i.e., normal derivative) boundary conditions in engineering blending. By following the previous papers, Parts I and II in Li (J. Comput. Math. 16 (1998) 457–480; J. Comput. Appl. Math. 110 (1999) 155–176) the corresponding theoretical analysis is made to discover that when the penalty power σ=2, σ=3 (or 3.5) and 0<σ1.5 in the boundary penalty finite element methods (BP-FEMs), optimal convergence rates, superconvergence and optimal numerical stability can be achieved, respectively. Several interesting samples of 3D blending surfaces are provided, to display the remarkable advantages of the proposed approaches in this paper: unique solutions of blending surfaces, optimal blending surfaces in minimum energy, ease in handling the complicated boundary constraint conditions, and less CPU time and computer storage needed. This paper and Li (J. Comput. Math. 16 (1998) 457–480; J. Comput. Appl. Math.) provide a foundation of blending surfaces by PDE solutions, a new trend of computer geometric design.